﻿//题目描述
//小e的背包容量为m，现在商店里有n 种商品。
//由于在梦境中，他可以零元购，但商品的数量有限，第i 种商品最多可以购买𝑠𝑖​件，
//每件商品有一个价值𝑤𝑖​和 体积𝑣𝑖。
//请问小e最多可以带走多少价值的商品？
//输入描述
//第一行：两个整数m, n，表示背包容量、商品种数。（1≤m, n≤2000）
//接下来n 行：每行三个整数𝑠𝑖,𝑤𝑖,𝑣𝑖​，表示第i 种商品的件数、价值、体积。（0≤𝑠𝑖,𝑤𝑖,𝑣𝑖≤2000）
//输出描述
//一个整数，表示小e能带走的最大价值。
//输入样例1
//10 3
//2 2 1
//1 5 3
//2 10 4
//输出样例1
//24
//样例解释：拿2 件商品1 和2 件商品3。
#include<bits/stdc++.h>
using namespace std;
const int N = 250;
typedef long long ll;
ll dp[N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ll m, n; cin >> m >> n;
	for (int i = 1; i <= n; ++i) {//二进制优化
		ll s, w, v; cin >> s >> w >> v;
		vector<ll>a;
		ll x = 1;
		while (s >= x) a.push_back(x),s-=x, x <<= 1;
		if (s)a.push_back(s);
		for (auto& k : a)
			for (int j = m; j >=k* v; --j)dp[j] = max(dp[j], dp[j - k*v] + k*w);
	}
	return 0;
}
//转换为0/1背包问题做法 时间复杂度较大，数据过大时就不行
// #include<bits/stdc++.h>
//using namespace std;
//const int N = 109;
//typedef long long ll;
//ll dp[N * N];
// int main() {
//ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//ll m, n; cin >> m >> n;
//for (int i = 1; i <= n; ++i) {
//	ll s, w, v; cin >> s >> w >> v;
//	while (s--) {//跑s次01背包
//		for (int j = m; j >= v; --j)
//			dp[j] = max(dp[j], dp[j - v] + w);
//	}
//	cout << dp[m] << '\n';
//}
//return 0;
//}